package com.fanshuai.algorithms.datastructure.graph;

import org.apache.commons.collections.CollectionUtils;

import java.util.*;

/**
 * 图  邻接表表示
 * @param <T>
 */
public class Graph2<T> implements IGraph<T> {
    static class LinkedNode { //邻接点
        public int dest;    //目标节点序号
        public int weight;  //权重

        public LinkedNode(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }

    private T[] nodes; //节点信息
    private int size;  //节点数量
    private Map<Integer, List<LinkedNode>> table; //邻接表
    private boolean direct; //是否为有向图

    public Graph2() {
        this.size = 256;
        this.direct = false;
        nodes = (T[])new Object[257];
        table = new HashMap<>();
    }

    public Graph2(int size, boolean direct) {
        this.size = size;
        this.direct = direct;

        nodes = (T[])new Object[size + 1];
        table = new HashMap<>();
    }

    @Override
    public void addEdge(int i, int j, int weight) {
        addEdgeDirect(i, j, weight);
        if (!direct) {
            addEdgeDirect(j, i, weight);
        }
    }

    @Override
    public void delEdge(int i, int j) {
        delEdgeDirect(i, j);
        if (!direct) {
            delEdgeDirect(j, i);
        }
    }

    private void addEdgeDirect(int i, int j, int weight) {
        List<LinkedNode> linkedNodes = table.get(i);
        if (null == linkedNodes) {
            linkedNodes = new ArrayList<>();
        }

        linkedNodes.add(new LinkedNode(j, weight));
        table.put(i, linkedNodes);
    }

    private void delEdgeDirect(int i, int j) {
        List<LinkedNode> linkedNodes = table.get(i);
        if (CollectionUtils.isNotEmpty(linkedNodes)) {
            Iterator<LinkedNode> iterator = linkedNodes.iterator();

            while (iterator.hasNext()) {
                LinkedNode node = iterator.next();
                if (node.dest == j) {
                    iterator.remove();
                }
            }
        }
        table.put(i, linkedNodes);
    }

    @Override
    public void setNodeInfo(int i, T node) {
        if (i <= 0 || i > size) {
            return;
        }
        nodes[i] = node;
    }

    @Override
    public T getNodeInfo(int i) {
        if (i <= 0 || i > size) {
            return null;
        }

        return nodes[i];
    }

    public int getSize() {
        return size;
    }

    public boolean getDirect() {
        return direct;
    }

    /**
     * 获取邻接点
     * @param src
     * @return
     */
    public List<Edge> getEdges(int src) {
        List<LinkedNode> linkedNodes = table.get(src);
        if (CollectionUtils.isEmpty(linkedNodes)) {
            return new ArrayList<>();
        }

        List<Edge> edges = new ArrayList<>();
        for (LinkedNode node : linkedNodes) {
            Edge edge = new Edge(src, node.dest, node.weight);
            edges.add(edge);
        }

        return edges;
    }

    /**
     * 获取所有边
     * @return
     */
    public List<Edge> getAllEdges() {
        List<Edge> edges = new ArrayList<>();
        for (int i = 1; i <= size; i++) {
            List<Edge> edges0 = getEdges(i);
            if (CollectionUtils.isEmpty(edges0)) {
                continue;
            }

            for (Edge edge : edges0) {
                if (direct) {
                    edges.add(edge);
                } else {
                    if (edge.src < edge.dest) { //无向图  每一条边的2个顶点有对称路径，因此需要去重
                        edges.add(edge);
                    }
                }
            }
        }

        return edges;
    }
}
